/*
 * @lc app=leetcode.cn id=15 lang=swift
 *
 * [15] 三数之和
 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 
 注意：答案中不可以包含重复的三元组。
 
 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 
 满足要求的三元组集合为：
 [
 [-1, 0, 1],
 [-1, -1, 2]
 ]
 */

// @lc code=start
// 说实话，这个题目有点难度
// 利用双指针
// 利用排序
// 以及怎么去重都是难题，利用排序。
class Solution15 {
    // 三数之和最好不用hash来做。
    // 要保证不重复。可以采用先排序。然后相同的不采用。
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        guard nums.count >= 3 else {
            return []
        }
        // o(nlong), 为了保证不重复，相连接的不能相同
        let sortedNums = nums.sorted()
        for i in 0..<sortedNums.count {
            if i > 0 && sortedNums[i] == sortedNums[i - 1] {
                continue
            }
            // 因为是有序的
            var left = i + 1
            var right = sortedNums.count - 1
            while left < right {
                let sum = sortedNums[left] + sortedNums[right] + sortedNums[i]
                if sum == 0 {
                    result.append([sortedNums[left], sortedNums[right], sortedNums[i]])
                    // 当相等时,p1 与 p2 去重
                    while left < right, sortedNums[left] == sortedNums[left + 1] {
                        left += 1
                    }
                    while left < right, sortedNums[right] == sortedNums[right - 1] {
                        right -= 1
                    }
                    right -= 1
                    left += 1
                } else if sum > 0 {
                    right -= 1
                } else {
                    left += 1
                }
            }
        }
        return result
    }
    static func test() {
        let solution = Solution15()
        let nums = [-1, 0, 1, 2, -1, -4]
        let result = solution.threeSum(nums)
        print(result)
    }
}

// @lc code=end

